1. Technical Field
The present invention relates to the field of simulation and, more particularly, to the simulation of electronic circuits within logic simulators.
2. Description of the Related Art
A logic simulator is a software tool which is capable of performing functional and timing simulations for digital electronic designs which are written in a hardware description language such as Very High Speed Integrated Circuits Hardware Description Language (VHDL) or Verilog. VHDL, for example, permits hardware designers to define signals at a very high level of abstraction. The abstracted signal representations can be translated to actual pins on a microchip using any of a variety of commercial electronic design automation (EDA) software tools.
Every logic simulator is equipped with an event queue. Future transactions, which refer to pairings of a new value for a particular signal and a time at which the signal assumes this new value, are scheduled to the event queue. The event queue has a listing of time slots, each of which can include one or more transactions pertaining to a particular signal within the design or to a group of signals within the design. The time slot indicates the time at which the referenced transactions are to occur.
During operation, or simulation, the simulation kernel requires that the event queue have the ability to locate and extract the next minimum time slot for which a transaction has been scheduled. Additionally, as transactions continue to arrive into the event queue during simulation, these new transactions must be scheduled. Accordingly, these new transactions are scheduled to the event queue by searching the event queue to determine whether a time slot already exists for this new transaction or one must be created.
Thus, in order to achieve suitable simulation performance, the event queue of a logic simulation tool must have the ability to quickly locate the next minimum time slot of all the time slots stored within the event queue, extract the minimum time slot quickly, insert a new time slot quickly, and search for an identified time slot. Conventional simulation tools utilize a priority queue as the event queue. The priority queue typically is implemented using a single data structure. In consequence, such event queues often perform well with respect to only one of the tasks an event queue must perform. This task varies with the particular data structure used to implement the priority queue.
In illustration, some conventional event queues are implemented using a binary tree data structure. A binary tree data structure provides for fast, efficient searching, insertion, and extraction, typically requiring a time period on the order of log N, where N is the total number of time slots within the binary tree. However, the log N time is based on a balanced binary tree, but, if used as an event queue, a binary tree typically is not going to be balanced. Instead, binary trees can degenerate into standard listings where most, if not all of the operations, require a time period on the order of N rather than log N.
More complex tree data structures, for example red and black trees, can provide log N complexity for the above operations and also maintain balance in the tree data structure. The amount of overhead needed for maintaining this balance, however, is significant and does little with respect to minimizing the time and resources necessary when utilizing this data structure.
Taking another example, hash table data structures also can be used to implement event queues. A hash table data structure provides for fast, efficient search for an identified time slot. This search time is typically about constant and generally does not increase as the number of entries increases. Hash table data structures, however, are not an efficient mechanism for locating the next minimum time slot. The complexity for locating and then extracting next minimum time slot from a hash table implementation is of the order of N.
The reliance upon logic simulation tools continues to increase with the complexity of logic designs. Accordingly, the aforementioned inefficiencies with respect to conventional event queues can significantly increase the time required to thoroughly test logic designs, thereby reducing simulation performance. What is needed is an improved event queue design and method for using the same.